package _2021._8._313_超级丑数;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 313
 * 超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
 * <p>
 * 给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
 * <p>
 * 题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
 */
public class Solution {
    public int nthSuperUglyNumber2(int n, int[] primes) {
        int ans = 0;
        Set<Long> seen = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        seen.add(1L);
        heap.offer(1L);
        for (int i = 0; i < n; i++) {
            //取出堆中的最小值
            long curr = heap.poll();
            ans = (int) curr;
            for (int prime : primes) {
                long next = curr * prime;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ans;
    }

    public int nthSuperUglyNumber(int n, int[] primes) {
        int i = 1;
        int count = 1;
        int ans = 1;
        while (count <= n) {
            int tmp = i;
            for (int prime : primes) {
                while (tmp % prime == 0) {
                    tmp /= prime;
                }
            }
            if (tmp == 1) {
                count++;
                ans = i;
            }
            i++;
        }
        return ans;
    }

    public static void main(String[] args) {
//        System.out.println(new LRUCache().nthSuperUglyNumber(12,new int[]{2,7,13,19}));
        System.out.println(new Solution().nthSuperUglyNumber2(100000, new int[]{7, 19, 29, 37, 41, 47, 53, 59, 61, 79, 83, 89, 101, 103, 109, 127, 131, 137, 139, 157, 167, 179, 181, 199, 211, 229, 233, 239, 241, 251}));
    }
}
